package com.leecode;

/**
 * 11. 盛最多水的容器
 *
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 *
 * 说明：你不能倾斜容器，且 n 的值至少为 2。
 * 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
 * 示例：
 * 输入：[1,8,6,2,5,4,8,3,7]
 * 输出：49
 */
public class Leet11 {
	public static void main(String[] args) {
		System.out.println(new Leet11().maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
	}

	/**
	 * 考点:index为0,height.length-1,明知距离越来短,移动矮边,最低水位线可以变高变矮(area还有希望变大),移动高边,最低水位线只可能更低,gg
	 * 92%,17%
	 */
	public int maxArea(int[] height) {
		int max=0;
		int b=0;
		int e=height.length-1;

		while(b<e){
			if(height[b]<height[e]){
				max=Math.max(max,height[b]*(e-b));//index:0和1之间相差1
				b++;
			}else{
				max=Math.max(max,height[e]*(e-b));
				e--;
			}
		}

		return max;
	}

	/**
	 * 100%,75%,自己想出来的,充份利用数学增函数的概念,缺点:写起来麻烦些
	 * 待优化
	 */
	public int maxArea2(int[] height) {
		int max=height[0];
		int maxWater=0;

		for(int i=0;i<height.length;i++){
			if(height[i]>max){
				max=height[i];
			}
		}

		int b=0;
		int e=height.length-1;

		h:
		for(int i=0;i<=max;i++){

			while(b<e){
				if(height[b]>=i){
					if(height[e]>=i){
						maxWater=(e-b)*i>maxWater?(e-b)*i:maxWater;
						i=maxWater/(e-b);
						continue h;
					}else{
						e--;
					}
				}else{
					b++;
				}
			}

			break h;
		}

		return maxWater;
	}
}
